NORMÁLNÍ FORMA GREIBACHOVÉ
Jedna ze standardizací podoby pravidel ↗bezkontextové gramatiky. Jestliže obecná bezkontextová gramatika obsahuje přepisovací pravidla typu X → α, kde X je neterminální symbol a α je řetězec složený z terminálů a/nebo neterminálů, pak bezkontextová gramatika v n.f.G. obsahuje jen pravidla jediného typu: X → aα, kde X je neterminální symbol, a je symbol terminální, α je řetězec buď prázdný, nebo složený výhradně z neterminálů (viz také ↗terminál a neterminál v syntaktické struktuře). Platí, že každý ↗bezkontextový jazyk s výjimkou takového, který obsahuje prázdný řetězec, se dá vygenerovat nějakou gramatikou v n.f.G. (prázdný řetězec se však v případě potřeby dá vygenerovat jediným zvláštním pravidlem S → λ, kde S je počáteční symbol gramatiky a λ prázdný řetězec). Znamená to, že pravidla každé bezkontextové gramatiky (s uvedenou výjimkou) lze převést do n.f.G. Generování/analýza bezkontextového jazyka v n.f.G. má tu výhodu, že pravá strana každého pravidla začíná terminálním symbolem, což umožňuje rychlejší ↗parsing, jelikož je odstraněna levá rekurze a aktuální symbol v právě zpracovávaném vstupu se snadno a rychle porovná s prvním symbolem pravidel gramatiky, přičemž se na aktuální vstup mohou aplikovat jen ta pravidla, jež mají terminál na své pravé straně roven aktuálnímu symbolu na vstupu. Gramatice v n.f.G. přesně odpovídá koncept zásobníkového automatu. Viz také ↗normální forma Chomského.
URL: https://www.czechency.org/slovnik/NORMÁLNÍ FORMA GREIBACHOVÉ (poslední přístup: 23. 11. 2024)
CzechEncy – Nový encyklopedický slovník češtiny
Všechna práva vyhrazena © Masarykova univerzita, Brno 2012–2020
Provozuje Centrum zpracování přirozeného jazyka